[POJ 2686] Traveling by Stagecoach

原题链接:[POJ 2686] Traveling by Stagecoach
原题大意:有mm个城市,nn张票.给定了起点和终点,以及两个城市之间的距离,假如两个城市之间是联通的,那么在使用一张车票的时候,会有tit_i只马的车载你到另一个城市,需要的时间是距离除马的数量.每张车票只能用一次现求从起点到终点最少时间是多少.
数据范围:
1n81 \leq n \leq 8
2m302 \leq m \leq 30

思路

由于数据量很小,在这种情况下考虑到指数级的算法可能的就是搜索和状压DPDP.这个题如果去掉车票的限制就是一个普通的最短路问题.如果要加入这个车票的限制,则在递推的时候也要把整个车票的状态全考虑进去,因此这就比较明显是一个状态压缩的形式:把所有的车票用二进制数压缩,11表示用了,将整个状态丢进去考虑再求最短路即可.
不过这题还有一个性质:可以发现从起点一直往外拓展的话,整个车票集合是只增不减的,也就是说如果把状态看成点,转移看成边,那么整个图是一个DAGDAG,即可以直接DPDP递推得到最后的答案.

状态设计

状态:$$f[S][v]表示当前手上的车票集合是S,,人在v$城市时最少要消耗多少时间,集合里如果是11表示已经用了,00表示没有用.
入口:f[0][a]=0f[0][a]=0一开始在aa城市,自然为00.由于要求最小值,因此其他为正无穷.
出口:minf[ ][b]min{f[~][b]}其中~表示任意的值,即只要能到vv即可.
转移:首先遍历起点vv,再遍历集合里每个元素,看哪个车票还没用,记为ii.再枚举谁是下一个到达的城市uu.这个过程就是从vvuu使用ii号车票.则实际产生的代价就是dist[v][u]/t[i]dist[v][u] / t[i].而后一个状态,也即是用掉了ii车票的状态记作S=S(1<<i)S' = S | (1 << i).表达式为f[S][u]=min(f[S][u],f[S][v]+dist[v][u]/t)f[S'][u] = min(f[S'][u],f[S][v] + dist[v][u] / t)

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;

int n,m,p,S,T;
const int N = 100,M = 10000,_N = 1 << 8;
const double INF = 1e12;
int dist[N][N];
double f[_N][N];
int t[N];
int main()
{
	while((scanf("%d%d%d%d%d",&n,&m,&p,&S,&T) == 5))
	{
		if(!n && !m && !p && !S && !T)	break;
		--S;--T;
		for(int i = 0;i < n;++i)	scanf("%d",&t[i]);
		for(int i = 0;i < 1 << n;++i)	fill(f[i],f[i] + m,INF);		
		for(int i = 0;i < m;++i)	fill(dist[i],dist[i] + m,-1);
		for(int i = 0;i < p;++i)
		{
			int u,v,w;scanf("%d%d%d",&u,&v,&w);
			--u;--v;
			dist[u][v] = dist[v][u] = w;
		}
		f[0][S] = 0;
		double res = INF;
		for(int state = 0;state < 1 << n;++state)
		{
			for(int v = 0;v < m;++v)
			{
				for(int i = 0;i < n;++i)
				{
					if(!(state >> i & 1))
					{
						for(int u = 0;u < m;++u)
						{
							if(dist[v][u] >= 0)
							{
								double rc = (double)dist[v][u] / t[i];
								int _state = state | (1 << i);
								f[_state][u] = min(f[_state][u],f[state][v] + rc);
							}
						}
					}
				}
			}
			res = min(res,f[state][T]);
		}
		if(res == INF)	printf("Impossible\n");
		else printf("%.3lf\n",res);
	}
    return 0;
}